#include <cstdio>
#include <cstdlib>
#include <stack>
#include <queue>
#include <string>
#include "StackSimulateQueue.h"

using namespace std;

int GetBracketIdx(char c, bool bLeft)
{
	char brackets[3][2] = {{'(', ')'}, {'[', ']'}, {'{', '}'}};
	for (int i = 0; i < 3; ++i)
	{
		if (bLeft && c == brackets[i][0])
		{
			return i;
		}
		else if (!bLeft && c == brackets[i][1])
		{
			return i;
		}
	}

	return -1;
}

bool IsBracketsMatch(const char* pattern)
{
	stack<char> BracketStack;
	int i = 0;
	while(char c = pattern[i++])
	{
		int leftIdx = GetBracketIdx(c, true);
		int rightIdx = GetBracketIdx(c, false);
		if (leftIdx >= 0)
		{
			BracketStack.push(c);
		}
		else if (rightIdx >= 0)
		{
			if (GetBracketIdx(BracketStack.top(), true) == rightIdx)
			{
				BracketStack.pop();
			}
			else
			{
				return false;
			}
		}
		else
		{
			return false;
		}
	}

	return BracketStack.empty();
}

void TestBracketsMatch()
{
	char* data[] = {"{}[](){[()]}",
					"{{{[[()]]}}",
					"{([)]}}",
					""};
	for (int i = 0; i < sizeof(data)/sizeof(data[0]); ++i)
	{
		if (IsBracketsMatch(data[i]))
		{
			printf("pattern %s match\n", data[i]);
		}
		else
		{
			printf("pattern %s not match\n", data[i]);
		}
	}
}

void TestStackSimulateQueue()
{
	StackSimulateQueue<int> sq;
	sq.push(1);
	sq.push(2);
	sq.push(3);
	printf("top is %d\n", sq.pop());
	sq.push(4);
	sq.push(5);
	printf("top is %d\n", sq.pop());
	printf("top is %d\n", sq.pop());
	printf("top is %d\n", sq.pop());
	printf("top is %d\n", sq.pop());
}

int main(int argc, char **argv)
{
	TestBracketsMatch();
	TestStackSimulateQueue();
	return 0;
}